package oct2013;

import java.util.Arrays;

public class ThreeSumClosest {
	public int threeSumClosest(int[] num, int target) {
		int n = num.length;
		Arrays.sort(num);
		int dist = Integer.MAX_VALUE;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				int v = target - num[i] - num[j];
				int k = Arrays.binarySearch(num, j + 1, n, v);
				if (k < 0) {
					k = -k - 1;
				} else {
					return target;
				}
				if (k < n && Math.abs(dist) > Math.abs(num[k] - v))
					dist = num[k] - v;
				if (k - 1 > j && Math.abs(dist) > Math.abs(num[k - 1] - v))
					dist = num[k - 1] - v;
			}
		}
		return target + dist;
	}

	public static void main(String[] args) {
		ThreeSumClosest a = new ThreeSumClosest();
		a.threeSumClosest(new int[] { 0, 1, 2 }, 0);
	}
}
